package datastructure.book.tujiesuanfa.list.solution._2_more;

import datastructure.book.tujiesuanfa.list.bean.ListNode;
import datastructure.book.tujiesuanfa.list.bean.Node;

public class Solution1 {

    /**
     * 给定一个头节点为 head 的链表，请查找并返回倒数第 cnt 个节点。
     * head就是链表的第一个元素
     * 1 <= cnt <= head.length
     * 例如：
     * 输入：head = [2,4,7,8], cnt = 1
     * 输出：8
     */
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode slow = head;ListNode fast = head;
        for (int i = 0; i < cnt; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /**
     * 递归实现
     */
    public ListNode trainingPlan2(ListNode head, int cnt){
        return trainingPlan0(head,cnt,new int[1]);
    }

    private ListNode trainingPlan0(ListNode head, int cnt,int[] curCnt){
        if (head == null) {
            return head;
        }
        ListNode listNode = trainingPlan0(head.next, cnt, curCnt);
        if (listNode != null) {
            return listNode;
        }
        curCnt[0]++;
        if (cnt == curCnt[0]) {
            return head;
        } else {
            return null;
        }
    }

    /**
     * 给定两升序链表 l1、l2，请升序合并这两个链表并返回。
     * 新链表是通过拼接给定的两个链表的所有节点组成的
     * 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
     * 输入：l1 = [], l2 = [] 输出：[]
     * 输入：l1 = [], l2 = [0] 输出：[0]
     */
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        //引入虚拟头结点简化代码
        ListNode result = new ListNode();
        ListNode pre = result;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                pre.next = l2;
                break;
            }
            if (l2 == null) {
                pre.next = l1;
                break;
            }
            if (l1.val > l2.val) {
                pre.next = l2;
                l2 = l2.next;
            } else {
                pre.next = l1;
                l1 = l1.next;
            }
            pre = pre.next;
        }
        ListNode temp = result.next;
        result.next = null;
        return temp;
    }

    /**
     * 复制链表，包括next指针和random指针
     * 使用O(N)时间复杂度和O(1)空间复杂度
     */
    public Node copyRandomList(Node head) {
        //使用自定义hash降低空间复杂度
        if (head == null) {
            return null;
        }
        Node temp = head;
        while (temp != null) {
            Node node = new Node(temp.val);
            node.next = temp.next;
            temp.next = node;
            temp = node.next;
        }
        temp = head;
        while (temp != null) {
            Node copy = temp.next;
            if (temp.random != null) {
                copy.random = temp.random.next;
            }
            temp = copy.next;
        }
        temp = head;
        Node copyResult = temp.next;
        while (temp != null) {
            Node copy = temp.next;
            temp.next = copy.next;
            temp = temp.next;
            if (copy.next != null) {
                copy.next = copy.next.next;
            }
        }
        return copyResult;
    }
}
